package leetcode.set_map;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.Set;

/**
 * 219. 存在重复元素 II
 * <p>
 * 给定一个整数数组和一个整数 k，判断数组中是否存在两个不同的索引 i 和 j，使得 nums [i] = nums [j]，并且 i 和 j 的差的 绝对值 至多为 k。
 * <p>
 * <p>
 * <p>
 * 示例 1:
 * <p>
 * 输入: nums = [1,2,3,1], k = 3
 * 输出: true
 * <p>
 * 示例 2:
 * <p>
 * 输入: nums = [1,0,1,1], k = 1
 * 输出: true
 * <p>
 * 示例 3:
 * <p>
 * 输入: nums = [1,2,3,1,2,3], k = 2
 * 输出: false
 * <p>
 * 分析： 两个长度至多为k  j-i<=k  也就说 i---j 有k+1个元素  如果当成滑动窗口，也就是说 窗口的长度保持不变，最多为 k+1,如果长度大于k+1
 * 就将前一个元素仍掉
 * 使用了hash 所以整体的时间复杂度为 o（n）
 * 空间复杂度 O(k)
 */
public class Solution219 {
    public static boolean containsNearbyDuplicate(int[] nums, int k) {
        Set<Integer> set = new HashSet<>();
        //循环遍历整个数组
        for (int i = 0; i < nums.length; i++) {
            int num = nums[i];
            if (set.contains(num)) {
                return true;
            }
            //不包含的话，进行往arrList添加元素，需要保证arrList长度不能超过k+1
            set.add(num);
            if (set.size() == k + 1) { //如果使用 arrayList 每次进行remove(0)时O(n)时间复杂度  显示超出时间限制
                set.remove(nums[i - k]);//移除的是k+1长度的第一个元素，
            }
        }

        return false;
    }

    public static void main(String[] args) {
        int[] nums = {1, 2, 3, 1, 2, 3};
        int k = 2;
        System.out.println(containsNearbyDuplicate(nums, k));
    }
}
